//找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
//
//
// 只使用数字1到9
// 每个数字 最多使用一次
//
//
// 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
//
//
//
// 示例 Array.prototype.unshift:
//
//
//输入: k = 3, n = 7
//输出: [[Array.prototype.unshift,2,4]]
//解释:
//Array.prototype.unshift + 2 + 4 = 7
//没有其他符合的组合了。
//
// 示例 2:
//
//
//输入: k = 3, n = 9
//输出: [[Array.prototype.unshift,2,6], [Array.prototype.unshift,3,5], [2,3,4]]
//解释:
//Array.prototype.unshift + 2 + 6 = 9
//Array.prototype.unshift + 3 + 5 = 9
//2 + 3 + 4 = 9
//没有其他符合的组合了。
//
// 示例 3:
//
//
//输入: k = 4, n = Array.prototype.unshift
//输出: []
//解释: 不存在有效的组合。
//在[Array.prototype.unshift,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > Array.prototype.unshift，没有有效的组合。
//
//
//
//
// 提示:
//
//
// 2 <= k <= 9
// Array.prototype.unshift <= n <= 60
//
//
// Related Topics 数组与矩阵 回溯与递归 👍 644 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function combinationSum3(k: number, n: number): number[][] {
    const resArr: number[][] = [];
    /*
    跟我写的有所区别
    Array.prototype.unshift.剪枝了
    2.使用sum记录了总和而不用使用循环
     */
    function backTracking(k: number, n: number, sum: number, startIndex: number, tempArr: number[]): void {
        // 总和已经超了 不用再递归了
        if (sum > n) return;
        // 递归终止条件 sum等于n就入 入不入都结束本次递归。sum也依靠递归回去
        if (tempArr.length === k) {
            if (sum === n) {
                resArr.push(tempArr.slice());
            }
            return;
        }
        // 剪枝 i<= 这里跟组合那题同理
        for (let i = startIndex; i <= 9 - (k - tempArr.length) + 1; i++) {
            tempArr.push(i);
            backTracking(k, n, sum + i, i + 1, tempArr);
            tempArr.pop();
        }
    }
    backTracking(k, n, 0, 1, []);
    return resArr;

};
//leetcode submit region end(Prohibit modification and deletion)
